What is handshake lemma?

The handshake lemma, also known as the handshaking theorem, is a basic result in graph theory that relates the sum of the degrees of the vertices in a graph to the total number of edges in the graph.

Formally, the handshake lemma states that the sum of the degrees of all the vertices in a graph is equal to twice the number of edges in the graph. In other words, if G is a graph with n vertices, and e edges, then

∑(deg(v)) = 2e

Where deg(v) is the degree of vertex v in the graph.

The handshake lemma is a fundamental result that is often used in graph theory proofs and can be applied to many different types of graphs. It is named after the concept of a handshake, where each edge "connects" two vertices in the graph, similar to how a handshake involves two people.